1. Field of the Invention
The present invention relates to computers and local area networks, and more particularly to an internal arbiter for a repeater in a standard Ethernet type network, which controls access to a common communication channel.
2. Related Art
Repeaters, also referred to as hubs or wiring concentrators, are in widespread use in local area networks. These devices allow interconnection of a number of network segments at the physical layer of the network protocol. Thus, in an Ethernet type network, devices coupled to a single repeater fall within the same collision detect domain for the physical layer of the local area network. See for example, U.S. Pat. No. 5,265,123, entitled EXPANDABLE REPEATER.
A repeater typically contains a number of ports which connect computer systems, thereby connecting the computer systems together through the repeater. Repeaters often connect to other repeaters through a common data channel such as an expansion port, thereby allowing communication between computer systems connected to different repeaters. In such a configuration, arbitration between repeaters is required to ensure that two or more repeaters do not transmit onto the common channel at the same time.
Arbitration can take place at a number of locations. It can take place externally to the repeaters at a centralized location. Or, it can take place internally, inside the repeaters, where each repeater contains a portion of the arbitration mechanism, and the arbitration mechanisms of a connected group of repeaters are coordinated through arbitration signals which are communicated between repeaters.
An external arbiter typically operates synchronously, with all repeaters tied to a common clock. During operation, repeaters send information to the external arbiter, which synchronously determines which repeaters intend to transmit. The centralized arbiter sends commands back to the repeaters, which: allow particular repeaters to transmit, block other repeaters from transmitting; and command other repeaters to transmit "jam patterns" over their general transmitting terminals. External arbitration circuits are implemented in a number of technologies including Programmable Array Logic (PAL), and Transistor-Transistor Logic (TTL).
A centralized external arbiter can be very useful in connecting a limited number of repeaters together. However, as the number of repeaters connected together increases, the number of signals connecting to the external arbiter increases, thereby increasing the number of pins required for a PAL which implements the external arbiter. This increases the cost of the PAL. Also, a centralized external arbiter cannot be easily scaled to accommodate additional repeaters, because if the number of repeaters exceeds the capacity of a particular external arbiter, the entire external arbiter must be replaced with a larger arbiter.
Alternatively, arbitration can take place internally. In one form, a bidirectional asynchronous line connects all repeaters, and each repeater has a unique device number. Before sending data across the communication channel connecting the repeaters together, a repeater transmits its device number across the asynchronous line, and concurrently reads the present device number from the asynchronous line. If these numbers are different, there must exist another repeater which intends to transmit across the communication channel. The repeater stops transmitting its device number to the asynchronous line, and sends "jam patterns" to its general transmitting terminals. If the repeater reads the same number that it sent across the asynchronous line, the repeater knows that it is the only repeater intending to transmit, so the repeater proceeds to transmit data across the communication channel.
Although this asynchronous interconnection scheme requires only a few wires to perform arbitration, the arbitration process is very time consuming. Repeaters must serially transmit their device numbers across the asynchronous line. Furthermore, the clock speed of this device number transmission is potentially very slow because the asynchronous line is bidirectional, and the asynchronous line may be very long if there are a large number of repeaters connected to it.
Alternatively, a daisy chain structure can be used to determine whether contention exists for access to the communication channel. In a daisy chain structure, repeaters are connected together in a linear chain through a sequence of directional daisy chain lines. Each repeater takes an input from a preceding repeater in the chain. This input indicates whether any of the preceding repeaters intend to transmit. If the input is asserted or if the repeater itself intends to transmit, the repeater asserts an output which feeds into the input of the next repeater of the chain. In this way, the daisy chain signal passes through all of the repeaters in the chain, and the signal is asserted when any of the repeaters intend to transmit.
In one embodiment, there are two parallel daisy chain lines connecting repeaters. One runs from the front of the chain to the back of the chain, and the other runs from the back of the chain to the front of the chain. Any repeater in the chain can determine if any other repeater in the chain intends to transmit by examining each of the daisy chain lines. Alternatively, a single daisy chain line runs from the front of the chain to the back of the chain, from where it makes a circular connection around to the front of the chain again.
A daisy chain structure has a number of advantages: it requires only simple interconnections, consisting of one or two lines running through the array; it requires only simple logic elements at each repeater; and it can be expanded to a large number of repeaters. However, a daisy chain structure has disadvantages. Each repeater in a daisy chain introduces at least one gate delay. Consequently, propagation delay through the daisy chain increases as the number of repeaters in the daisy chain increases. This can sharply limit the number of repeaters which can be connected together in a practical system.
Another method for detecting contention is through a "wiring array," which comprises a set of wires running through all of the repeaters. Each repeater connects to its own wire, on which the repeater broadcasts its intention to transmit. A repeater detects whether other repeaters intend to transmit by examining the wires from other repeaters. There is very little propagation delay in this wiring array structure, because each wire runs unimpeded through all of the repeaters in the array, without passing through a logic gate, or other circuitry. Contention detection is therefore very fast. However, connecting large numbers of repeaters in this manner requires a large number of wires running between repeaters. For example, 32 repeaters would require 32 wires. This wiring complexity grows prohibitively large as the number of repeaters increases. Additionally, the number of wires running through repeaters is fixed for a given wiring array implementation, making it impossible to expand a given wiring array past a fixed number of repeaters.
What is needed is a contention detection mechanism which combines the rapid speed of a wiring array structure and the scalability of a daisy chain structure.